/**
 * @param {number[]} nums
 * @return {number}
 */
// 先做过去
var majorityElement = function (nums) {
  let map = {}
  const len = nums.length
  for (let i = 0; i < len; i++) {
    if (map[nums[i]]) {
      map[nums[i]]++
    } else {
      map[nums[i]] = 1
    }
  }
  for (let n of nums) {
    if (map[n] > Math.floor(len / 2)) {
      return n
    }
  }
}
// 第二种方法排序，直接取中间的数就行
var majorityElement1 = function (nums) {
  nums.sort()
  const len = nums.length
  return nums[Math.floor(len / 2)]
}
// 时间on，空间o1怎么做？摩尔投票算法，用来求解众数
var majorityElement3 = function (nums) {
  let count = 0 // 票数
  let candidate = nums[0] // 候选人
  for (let i = 0; i < nums.length; i++) {
    if (count == 0) {
      candidate = nums[i]
    }
    if (candidate == nums[i]) {  // 票数+1
      count++
    } else {  // 票数-1
      count--
    }
  }
  return candidate
}